package leetcode;

import java.util.PriorityQueue;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q0215.java
 * @Author : WangRuoyu
 * @Date 2023/11/16 21:53
 */


public class Q0215 {
    /*** 堆排序 ***/
//    public int findKthLargest(int[] nums, int k) {
//        PriorityQueue<Integer> pq = new PriorityQueue<>();
//        for (int i = 0; i < k; i++) {
//            pq.add(nums[i]);
//        }
//        for (int i = k; i < nums.length; i++) {
//            if (nums[i] > pq.peek()) {
//                pq.poll();
//                pq.add(nums[i]);
//            }
//        }
//        return pq.peek();
//    }

    /*** 快排优化 ***/
    public int findKthLargest(int[] nums, int k) {
        return quickSort(nums, nums.length - k, 0, nums.length - 1);
    }

    private int quickSort(int nums[], int k, int l, int r) {
        if (l >= r) return nums[l];

        int x = nums[l + r >> 1];
        int i = l - 1;
        int j = r + 1;
        while (i < j) {
            while (nums[++i] < x) ;
            while (nums[--j] > x) ;
            if (i < j) {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }

        return k <= j ? quickSort(nums, k, l, j) : quickSort(nums, k, j + 1, r);
    }

    //    private int quickSort(int nums[], int k, int l, int r) {
//        if (l == r) return nums[l];
//        int x = nums[l + r >> 1];
//        int i = l - 1;
//        int j = r + 1;
//        while (i < j) {
//            while (nums[++i] < x) ;
//            while (nums[--j] > x) ;
//            if (i < j) {
//                int tmp = nums[i];
//                nums[i] = nums[j];
//                nums[j] = tmp;
//            }
//        }
//        if (k <= j) return quickSort(nums, k, l, j);
//        else return quickSort(nums, k, j + 1, r);
//    }
    public static void main(String[] args) {
        Q0215 sl = new Q0215();
    }
}